#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct btrees
{
	int data;
	struct btrees *left;
	struct btrees *right;
}btree;

typedef struct queue
{
	btree *data;
	struct queue *next;
}bqueue;

int enqueue(bqueue **head,bqueue **tail,btree **data)
{
	bqueue *temp;
	temp=(bqueue *)malloc(sizeof(bqueue));
	temp->data=(*data);
	temp->next=NULL;
	if((*head)==NULL)
	{
		(*head)=temp;
		(*tail)=temp;
	}
	else
	{
		(*tail)->next=temp;
		(*tail)=temp;
	}
}

btree *dequeue(bqueue **head,bqueue **tail)
{
	if((*head)==NULL) return NULL;
	bqueue *temp;
	btree *tmp;
	temp=(*head);
	tmp=temp->data;
	if((*head)->next==NULL)
	{
		(*head)=NULL;
		(*tail)=NULL;
	}
	else
	{
		(*head)=(*head)->next;
	}
	free(temp);
	return tmp;
}

int btreemax(btree **head)
{
	btree *tmp;
	tmp=(*head);
	while(tmp->right!=NULL)
	{
		tmp=tmp->right;
	}
	return tmp->data;
}

int btreemin(btree **head)
{
	btree *tmp;
	tmp=(*head);
	while(tmp->left!=NULL)
	{
		tmp=tmp->left;
	}
	return tmp->data;
}

int btreeinsert(btree **head,int data)
{
	btree *temp;
	if((*head)==NULL)
	{
		temp=(btree *)malloc(sizeof(btree));
		temp->data=data;
		temp->left==NULL;
		temp->right=NULL;
		(*head)=temp;
	}
	else
	{
		((*head)->data>data)?(btreeinsert(&(*head)->left,data)):(btreeinsert(&(*head)->right,data));
	}
}

int btreesearch(btree **head,int data)
{
	if((*head)==NULL) return 0;
	if((*head)->data==data) return 1;
	((*head)->data>data)?(btreesearch(&(*head)->left,data)):(btreesearch(&(*head)->right,data));
}

int freebtree(btree **head)
{
	if((*head)!=NULL)
	{
		freebtree(&(*head)->left);
		freebtree(&(*head)->right);
		free((*head));
	}
}

int btreeinorder(btree **head)
{
	if((*head)!=NULL)
	{
		btreeinorder(&(*head)->left);
		printf("%d ",(*head)->data);
		btreeinorder(&(*head)->right);
	}
}

int btreepreorder(btree **head)
{
	if((*head)!=NULL)
	{
		printf("%d ",(*head)->data);
		btreepreorder(&(*head)->left);
		btreepreorder(&(*head)->right);
	}
}

int btreepostorder(btree **head)
{
	if((*head)!=NULL)
	{
		btreepostorder(&(*head)->left);
		btreepostorder(&(*head)->right);
		printf("%d ",(*head)->data);
	}
}

int btreeheight(btree **head)
{
	int h=1;
	int hl,hr;
	if((*head)==NULL) return -1;
	hl=btreeheight(&(*head)->left);
	hr=btreeheight(&(*head)->right);
	h+=(hl>hr)?hl:hr;
	return h;
}

int btreebfs(btree **head)
{
	int i,j;
	btree *temp;
	temp=(*head);
	bqueue *qhead=NULL;
	bqueue *qtail=NULL;
	i=1;
	j=0;

//	while(temp!=NULL)
//	{
//		printf("%d ",temp->data);
//		if(temp->left!=NULL) enqueue(&qhead,&qtail,&temp->left);
//		if(temp->right!=NULL) enqueue(&qhead,&qtail,&temp->right);
//		temp=dequeue(&qhead,&qtail);
//	}

	while(temp!=NULL)
	{
		if(i!=0)
		{
			printf("%d ",temp->data);
			if(temp->left!=NULL) 
			{
				j++;
				enqueue(&qhead,&qtail,&temp->left);
			}
			if(temp->right!=NULL) 
			{
				enqueue(&qhead,&qtail,&temp->right);
				j++;
			}
			temp=dequeue(&qhead,&qtail);
			i-=1;
		}
		else
		{
			printf("\n");
			i=j;
			j=0;
		}
	}
}

int btreelca(btree **head,int i,int j)
{
	int l,r,m;
	btree *tmp;
	tmp=(*head);
	(i>j)?(r=i,l=j):(r=j,l=i);
	if(tmp==NULL||tmp->data==i||tmp->data==j) return -1;
//	while(tmp!=NULL)
//	{
//		if(tmp->left!=NULL&&(tmp->left->data==i||tmp->left->data==j)) return tmp->data;
//		if(tmp->right!=NULL&&(tmp->right->data==i||tmp->right->data==j)) return tmp->data;
//		if(tmp->data<i) 
//		{
//			tmp=tmp->right;
//			continue;
//		}
//		if(tmp->data>j)
//		{
//			tmp=tmp->left;
//			continue;
//		}
//		printf("%d \n",tmp->data);
//	}
	while(tmp!=NULL)
	{
		if(tmp->data>r)
		{
			m=tmp->left->data;
			if(m==l||m==r) return tmp->data;
			tmp=tmp->left;
			continue;
		}
		if(tmp->data<l)
		{
			m=tmp->right->data;
			if(m==l||m==r) return tmp->data;
			tmp=tmp->right;
			continue;
		}
		return tmp->data;
	}
	return -1;
}




int main()
{
	int i,j,k;
	int n;
	int *p;
	btree *head=NULL;
	scanf("%d",&n);
	p=(int *)malloc(n*sizeof(int));
	for(i=0;i<n;i++) scanf("%d",&p[i]);
	for(i=0;i<n;i++) btreeinsert(&head,p[i]);
	printf("3 is %d \n",btreesearch(&head,3));
	printf("6 is %d \n",btreesearch(&head,6));
	btreeinorder(&head);
	printf("\n");
	btreepreorder(&head);
	printf("\n");
	btreepostorder(&head);
	printf("\n");
	printf("height of btree is %d\n",btreeheight(&head));
	btreebfs(&head);
	printf("min is %d \n",btreemin(&head));
	printf("max is %d \n",btreemax(&head));
	printf("lca of 3 and 5 is %d \n",btreelca(&head,3,5));
	printf("lca of 3 and 8 is %d \n",btreelca(&head,3,8));
	freebtree(&head);
	free(p);
	return 0;
}


